#include <iostream>
#include <vector>
using namespace std;

vector<int> helan4(vector<int> &nums, int l, int r) {
  if (l > r) {
    return {-1, -1};
  }
  
  if (l == r) {
    return {l, r};
  }

  int pointsmall = l - 1;
  int pointmore = r;
  int point = l;
  int target = nums[r];
  while (point < pointmore) {
    if (nums[point] < target) {
      swap(nums[point++], nums[++pointsmall]);
    } else if (nums[point] == target) {
      ++point;
    } else {
      swap(nums[point], nums[--pointmore]);
    }
  }
  swap(nums[pointmore], nums[r]);
  return {pointsmall + 1, pointmore};
}


/*
 *随机数版本可以将随机位置与r交换
 * */
void quicksort(vector<int> &nums, int l, int r) {
  vector<int> res = helan4(nums, l, r);
  quicksort(nums, l, res[0] - 1);
  quicksort(nums, res[1] + 1, r);
}

/*
 *非递归版本用栈来模拟递归，大数据可能有优势
 */

int main() {}
